class Solution {//leetcode22——括号生成
private:
    void dfs(int n){
        if(left_cnt>n||right_cnt>n) return;
        if(left_cnt<right_cnt) return;
        if(left_cnt==n&&right_cnt==n){
            ret.push_back(path);
            return;
        }
        path.push_back('(');
        left_cnt++;
        dfs(n);
        path.pop_back();
        left_cnt--;

        path.push_back(')');
        right_cnt++;
        dfs(n);
        path.pop_back();
        right_cnt--;
    }
public:
    vector<string> generateParenthesis(int n) {
        dfs(n);
        return ret;
    }
private:
    vector<string> ret;
    string path;
    int left_cnt;//左括号个数
    int right_cnt;//右括号个数
};